package leetcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class MutiplyStrings {
	public String multiply(String num1, String num2) {
		if (num1 == null || num2 == null || num1.length() == 0
				|| num2.length() == 0)
			return null;

		if ("0".equals(num1) || "0".equals(num2))
			return "0";

		List<String> li = new ArrayList<String>();
		int maxLen = 0;
		for (int i1 = num1.length() - 1; i1 >= 0; i1--) {
			int carry = 0;
			StringBuilder b = new StringBuilder();
			for (int i2 = num2.length() - 1; i2 >= 0; i2--) {

				Integer res = Character.getNumericValue(num1.charAt(i1))
						* Character.getNumericValue(num2.charAt(i2)) + carry;
				b.insert(0, res % 10);
				carry = res / 10;
			}

			if (carry != 0)
				b.insert(0, carry);

			for (int t = 0; t < num1.length() - 1 - i1; ++t)
				b.append('0');

			li.add(b.reverse().toString());

			maxLen = maxLen < b.length() ? b.length() : maxLen;
		}

		StringBuilder fres = new StringBuilder();
		int scarry = 0;
		for (int p = 0; p < maxLen; ++p) {
			int sum = 0;

			for (String str : li) {
				if (p < str.length())
					sum += Character.getNumericValue(str.charAt(p));
			}
			sum += scarry;
			fres.append(sum % 10);
			scarry = sum / 10;
		}

		if (scarry != 0)
			fres.append(scarry);

		return fres.reverse().toString();
	}

	@Test
	public void testResult() {
		MutiplyStrings ms = new MutiplyStrings();
		System.out.println(ms.multiply("54506613011237113799160685650235886", "779900149252161221008788"));
	}
}
